The present invention relates to streaming graphs, and more specifically, to methods and systems for identifying clusters in a streaming graph.
Graphs are effective tools for representing collections of relationships between entities. These relationships could be, for example, social ties between people, communications links between computer systems, links between web-pages, transportation channels between locations, or chemical bonds between atoms or molecules. Graphs are rich sources of information regarding how the entities behave and interact with each other. The field of graph analytics, or graph data mining, is devoted to understanding and decoding this information by studying structural properties of the graph and observing how graphs evolve with time. This information can then be put to use in several applications like online marketing, ranking search results, recommendation systems, churn prediction in mobile networks, disease control and drug discovery, to name a few.
One area of graph analytics includes the clustering or partitioning of nodes, or vertices, of graphs. Graph clustering has been the subject of research mainly in an offline setting where the entire graph is given beforehand. Graph clustering has been used for a wide variety of applications such as detecting communities in social networks, constructing phylogenetic trees or analyzing human genes, and load balancing in distributed computing. However, current clustering methods are not suitable for use with streaming graphs where the updates to the graph include streaming edge and/or vertex additions or deletions.